'''
https://leetcode.cn/problems/graph-valid-tree/description/
'''
from typing import List

class UF:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.sets = n
    def find(self,x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    def union(self,x,y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy: return False
        self.father[fy] = fx
        self.sets -= 1
        return True

class Solution:

    # 1）只有一个根节点
    # 2）且无环

    # 并查集
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        uf = UF(n)
        for u, v in edges:
            if not uf.union(u, v):
                return False
        return uf.sets == 1
    # dfs
    def validTree2(self, n: int, edges: List[List[int]]) -> bool:
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        visited = [False] * n

        def f(u, father):
            if visited[u]: return False
            visited[u] = True
            for v in graph[u]:
                if v == father: continue
                if not f(v, u):
                    return False
            return True
        return f(0, -1) and all(visited)